package 力扣.动态规划;
//有 n 个城市通过 m 个航班连接。每个航班都从城市 u 开始，以价格 w 抵达 v。
//
//现在给定所有的城市和航班，以及出发城市 src 和目的地 dst，
// 你的任务是找到从 src 到 dst 最多经过 k 站中转的最便宜的价格。 如果没有这样的路线，则输出 -1。

import java.util.Arrays;

public class 寻找k站中转航班 {
    public static void main(String[] args) {

    }
    public static int findCheapestPrice(int n, int[][] flights, int src, int dst, int K) {
        //定义dp数组  换乘K次，到达dst
        int[][] dp = new int[K+1][n];
        for (int i = 0; i < K + 1; i++) {
            Arrays.fill(dp[i], Integer.MAX_VALUE);
        }
        //初始化直达的班次
        for (int[] flight : flights) {
            if (flight[0]==src)
                    dp[0][flight[1]]=flight[2];
        }
        //初始化目的地为src的班次
        for (int i = 0; i <K+1; i++) {
            dp[i][src]=0;
        }
        for (int i = 1; i < K+1; i++) {
            for (int[] flight: flights) {
                if (dp[i-1][flight[0]]!= Integer.MAX_VALUE){
                    dp[i][flight[1]]=Math.min(dp[i][flight[1]],dp[i-1][flight[0]]+flight[2]);
                }
            }
        }
        return dp[K][dst]== Integer.MAX_VALUE?-1:dp[K][dst];
    }
}
